import java.util.Arrays;
import java.lang.Math;
public class TestDemo {

    /*
    public static void swap(int[] array, int min, int i) {

        int t = array[min];
        array[min] = array[i];
        array[i] = t;
    }

    public static void selectionSort(int[] array) {
        int min = 0;
        for (int i = 0;i < array.length;i++) {
            min = i;
            for (int j = i + 1;j<array.length;j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            swap(array,min,i);
        }
    }

    public static void main(String[] args) {
        int[] array = {1,1,5,7,9,2,4,4,8,10};
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }
    */

    /*
    public static int process(int[] array,int l ,int r) {

        if (l == r) {
            return array[l];
        }
        int mid = l + ((r - l)>>>1);
        int leftMax = process(array, l, mid);
        int rightMax = process(array,mid+1, r);
        return Math.max(leftMax,rightMax);
    }

    public static int getMax(int[] array) {
        int l = 0, r = array.length - 1;
        return process(array, l, r);
    }

    public static void main(String[] args) {
        int[] array = {1,3,10,2,8,23,15,0,4};
        int max = getMax(array);
        System.out.println(max);
    }
     */

    /*
    public static void Merge(int[] array, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l, p2 = mid + 1, i = 0;
        while ((p1 <= mid) && (p2 <= r)) {
            help[i++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
        }

        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= r) {
            help[i++] = array[p2++];
        }

        for (i = 0;i<help.length;i++) {
            array[l + i] = help[i];
        }


    }

    public static void process(int[] array, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l)>>>1);
        process(array, l ,mid);
        process(array, mid + 1, r);
        Merge(array, l , mid, r);
    }

    public static void mergeSort(int[] array) {
        process(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        int[] array = {5,6,4,9,8,12,13,14,0,28};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
     */

    public static int merge(int[] arr,int l, int mid, int r) {
        int p1 = l, p2 = mid + 1, res = 0, i = 0;
        int[] help = new int[r - l + 1];
        while ((p1 <= mid) && (p2 <= r)) {
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0;i < help.length;i++) {
            arr[l + i] = help[i];
        }
        return res;
    }

    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l)>>>1);
        return process(arr, l ,mid) +
                process(arr, mid + 1, r ) +
                merge(arr, l, mid, r);
    }

    public static int smallSum(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }


    public static void main(String[] args) {
        int[] arr1 = {1,3,4,2,5};
        int ret1 = smallSum(arr1);
        System.out.println(ret1);
    }
}
